https://www.acmicpc.net/problem/2751

아주 긴 수열을 오름차순 정렬하는 문제

병합 정렬을 사용해 시간 복잡도를 낮춰야 함

병합 정렬 사용

def merge_sort(array):
    if len(array) <= 1:
        return array

    mid = len(array) // 2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])

    i, j, k = 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1

    while i < len(left):
        array[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        array[k] = right[j]
        j += 1
        k += 1

    return array

n = int(input())
array = []
for _ in range(n):
    array.append(int(input()))

array = merge_sort(array)
for data in array:
    print(data)

파이썬 모듈 사용

n = int(input())
array = []
for _ in range(n):
    array.append(int(input()))

array = sorted(array)
for data in array:
    print(data)